#include "ConvexSet.h"

namespace poly
{
	void ConvexSet::initialize( Polygon P )
	{
		m_polygons.clear();
		if( P.size() < 3 ) return;

		while( P.size() > 2 )
		{
			m_polygons.push_back( clipConvex( P ) );
		}
	}

	ConvexSet::ConvexSet( Polygon const & P )
	{
		initialize( P );
	}

	PolygonList ConvexSet::polygonList() const
	{
		return m_polygons;
	}

	Polygon ConvexSet::clipConvex( Polygon & P )
	{
		for( int i = 0; i < P.size(); i++ )
		{
			int f = i;
			int p = i;

			for( int e0 = (i + 1)%P.size(); e0 != i; e0=(e0+1)%P.size() )
			{
				int e1 = (e0 + 1)%P.size();

				if( !rightHanded( P[p], P[e0], P[e1] ) )
				{
					break;
				}

				if( !rightHanded( P[i], P[e0], P[e1] ) )
				{
					break;
				}

				bool empty = true;
				for( int rest = (e1 + 1)%P.size(); rest != i; rest=(rest+1)%P.size() )
				{
					bool rightHanded1 = rightHanded( P[i], P[e0], P[rest] );
					bool rightHanded2 = rightHanded( P[e0], P[e1], P[rest] );
					bool rightHanded3 = rightHanded( P[e1], P[i], P[rest] );
					if( (
						rightHanded1 &&
						rightHanded2 &&
						rightHanded3
						) )
					{
						empty = false;
						break;
					}
				}

				if( !empty )
				{
					break;
				}

				f = e1;

				p = e0;
			} // for e0

			if( f != i )
			{
				Polygon out;
				out.insert( out.begin(), P.begin()+i, P.begin()+f+1 );
				P.erase( P.begin()+i+1, P.begin()+f );

				return out;
			}
		} // for i

		Polygon out;
		return out;
	}
}
